Computer graphics is used in a wide variety of applications, such as in business, science, animation, simulation, computer-aided design, process control, electronic publishing, gaming, medical diagnosis, etc. In those applications, three-dimensional (3D) graphical objects are displayed on a computer screen by using a number of polygons to represent the three-dimensional objects. In order to portray a more realistic real-world representation, texture mapping is usually applied. Texture mapping refers to techniques for using two-dimensional (2D) texture images, or texture maps, for adding surface details to areas or surfaces of these 3D graphical objects. For example, given a featureless solid cube and a texture map defining a wood grain pattern, texture mapping techniques may be used to map the wood grain pattern onto the cube. The resulting image is that of a cube that appears to be made of wood. In another example, vegetation and trees can be added by texture mapping to an otherwise barren terra model in order to portray a landscape filled with vegetation and trees.
In computer systems having dedicated graphics hardware, images for use in texture mapping are typically stored in memory in the form of a collection of tiles. These tiles are addressed and managed as a virtually contiguous region of address space by a two-dimensional index (S,T). In other words, this memory management scheme treats a texture map as an array of small, contiguous tiles each including a number of texels. Thereby, memory management issues, such as caching, virtual-to-physical mapping, swapping, etc. are more easily executed.
In order to utilize computer resources more efficiently, computer graphics systems typically include a graphics co-processor for offloading processing burdens from the CPU of the computer system, and a texture memory for storing the texture data. Moreover, in order to further accelerate the texture mapping process, a special cache memory, also known as a texture cache, may also be implemented in the computer graphics systems for providing faster access to and temporary storage of frequently used tiles of texture data.
Texture caches, like other types of cache memories, are much smaller in capacity than the texture memory to which they are mapped. To this end, texture caches may be mapped to the local memory according to one of a plurality of mapping schemes. FIG. 1 illustrates, as an example, a prior art direct-mapping scheme for mapping texture memory to texture cache. As shown in FIG. 1, texture map 50 consists of texture data tiles 0 to 3 in the first row, texture data tiles 4-7 in the second row, texture data tiles 8-11 in the third row, and texture data tiles 12-15 in the fourth row. On the other hand, texture cache 20 is made up of cache lines 0-3 in the first row and cache lines 4-7 in the second row. In this mapping scheme, texture data tiles within the same column are mapped to the same cache lines in the texture cache. For instance, as illustrated in FIG. 1, texture tiles 0 and 8 are mapped to cache line 0, texture tiles 4 and 12 are mapped to cache line 4, and texture tiles 7 and 15 are mapped to cache line 7, etc.
Prior art direct-mapping schemes, such as the one illustrated in FIG. 1, have the advantage of simplicity. However, the prior art direct-mapping schemes have the disadvantage that only a single texture data tile from a given group can be present in the texture cache at a given time. That is, if two texture data tiles from the same group are frequently referenced, thrashing--repeated moving of the two tiles in and out of the cache--will occur. Unfortunately, in texture mapping, texture data tiles are commonly accessed one row or one column at a time for display or processing. For example, it is not uncommon for a particular column of the texture map 50 to be referenced frequently. In that situation, thrashing may occur, drastically reducing the usefulness and speed of the texture cache 20. Therefore, prior art direct-mapping schemes are not ideal for the purposes of caching texture maps.
In order to provide for a more flexible caching method, other cache-mapping schemes, such as fully associative mapping, and set-associative mapping, may be used. However, those cache-mapping schemes are complicated, and implementations of such schemes require a large number of gates. Naturally, these extra gates unnecessarily increase manufacturing costs of the integrated circuits and consume large amounts of valuable die area. Therefore, what is needed is a caching scheme that has the advantage of simplicity, and yet, has the flexibility to accommodate portions of texture maps that have a wide aspect ratio such that thrashing is reduced.